In packet-switching communications networks, user information is carried in packets which are routed from the source towards the destination via switches or routers. The switch buffers each packet received from the upstream direction until a decision is made when and on which outgoing link the packet would be forwarded. The time that a packet takes to reach the destination after it leaves the source is called end-to-end packet delay. Different packets travelling between the same source/destination pair may experience different delays which depend on traffic conditions and level of congestion in different switches, scheduling and management policy, and other deterministic and/or random factors.
The end-to-end delay accumulates the link transmission delays, propagation delays and switch processing delays along the route. Whereas the transmission delays and propagation delays are determined by the packet size and the fixed link parameters (capacity, length and signal propagation speed in the medium) and therefore are predictable with small error, the switch processing delays are subject to much larger random deviations. The single main contributor to the switch processing delay is the queuing delay in a switch's buffer.
In-service measurement of packet delay in a switch is an important source of network management information. It allows the switch to monitor the existing level of congestion, to provision a selected quality-of-service, as well as to support other management functions, including admission of a new connection, path selection and load balancing.
The in-service measurements are required on a per-flow basis, i.e., with respect to specific spatial source-destination pairs and to specific packet loss and service priorities. Since the delays of individual packets are experienced at arbitrary moments of time and are, therefore, random variables, the values arrived at in the course of measurement are merely samples from a stochastic process, and therefore require an estimation procedure.
Conventional direct measurements are based on timestamping. When a packet is enqueued, it is assigned a numerical value associated with the current time or clock cycle number. This value is stored with the packet. When the packet is dequeued, the difference between the new current time or clock cycle number and the value stored with the packet constitute a sampled queuing delay. However, packet timestamping in a high-speed packet switch where the number of the simultaneously buffered packets is significantly large incurs significant overhead associated with the buffer space allocated for the timestamps. Therefore, in high-speed packet switches, the direct measurement methods may be unavailable or undesirable.